use crate::src::struct_and_type::{
    AVLTree, AVLTreeCompareFunc, AVLTreeKey, AVLTreeNode, AVLTreeNodeSide, AVLTreeValue,
};

extern "C" {
    fn malloc(_: u64) -> *mut ();
    fn free(_: *mut ());
}
pub const AVL_TREE_NODE_RIGHT: AVLTreeNodeSide = 1;
pub const AVL_TREE_NODE_LEFT: AVLTreeNodeSide = 0;
#[no_mangle]
pub extern "C" fn avl_tree_new(mut compare_func: AVLTreeCompareFunc) -> *mut AVLTree {
    let mut new_tree: *mut AVLTree = 0 as *mut AVLTree;
    new_tree = (unsafe { malloc(::core::mem::size_of::<AVLTree>() as u64) }) as *mut AVLTree;
    if new_tree.is_null() {
        return 0 as *mut AVLTree;
    }
    (unsafe { (*new_tree).root_node = 0 as *mut AVLTreeNode });
    (unsafe { (*new_tree).compare_func = compare_func });
    (unsafe { (*new_tree).num_nodes = 0 as u32 });
    return new_tree;
}
extern "C" fn avl_tree_free_subtree(mut tree: *mut AVLTree, mut node: *mut AVLTreeNode) {
    if node.is_null() {
        return;
    }
    avl_tree_free_subtree(tree, unsafe {
        (*node).children[AVL_TREE_NODE_LEFT as i32 as usize]
    });
    avl_tree_free_subtree(tree, unsafe {
        (*node).children[AVL_TREE_NODE_RIGHT as i32 as usize]
    });
    (unsafe { free(node as *mut ()) });
}
#[no_mangle]
pub extern "C" fn avl_tree_free(mut tree: *mut AVLTree) {
    avl_tree_free_subtree(tree, unsafe { (*tree).root_node });
    (unsafe { free(tree as *mut ()) });
}
#[no_mangle]
pub extern "C" fn avl_tree_subtree_height(mut node: *mut AVLTreeNode) -> i32 {
    if node.is_null() {
        return 0;
    } else {
        return unsafe { (*node).height };
    };
}
extern "C" fn avl_tree_update_height(mut node: *mut AVLTreeNode) {
    let mut left_subtree: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut right_subtree: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut left_height: i32 = 0;
    let mut right_height: i32 = 0;
    left_subtree = unsafe { (*node).children[AVL_TREE_NODE_LEFT as i32 as usize] };
    right_subtree = unsafe { (*node).children[AVL_TREE_NODE_RIGHT as i32 as usize] };
    left_height = avl_tree_subtree_height(left_subtree);
    right_height = avl_tree_subtree_height(right_subtree);
    if left_height > right_height {
        (unsafe { (*node).height = left_height + 1 });
    } else {
        (unsafe { (*node).height = right_height + 1 });
    };
}
extern "C" fn avl_tree_node_parent_side(mut node: *mut AVLTreeNode) -> AVLTreeNodeSide {
    if (unsafe { (*(*node).parent).children[AVL_TREE_NODE_LEFT as i32 as usize] }) == node {
        return AVL_TREE_NODE_LEFT;
    } else {
        return AVL_TREE_NODE_RIGHT;
    };
}
extern "C" fn avl_tree_node_replace(
    mut tree: *mut AVLTree,
    mut node1: *mut AVLTreeNode,
    mut node2: *mut AVLTreeNode,
) {
    let mut side: i32 = 0;
    if !node2.is_null() {
        (unsafe { (*node2).parent = (*node1).parent });
    }
    if (unsafe { (*node1).parent }).is_null() {
        (unsafe { (*tree).root_node = node2 });
    } else {
        side = avl_tree_node_parent_side(node1) as i32;
        (unsafe { (*(*node1).parent).children[side as usize] = node2 });
        avl_tree_update_height(unsafe { (*node1).parent });
    };
}
extern "C" fn avl_tree_rotate(
    mut tree: *mut AVLTree,
    mut node: *mut AVLTreeNode,
    mut direction: AVLTreeNodeSide,
) -> *mut AVLTreeNode {
    let mut new_root: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    new_root =
        unsafe { (*node).children[(1 as i32 as u32).wrapping_sub(direction as u32) as usize] };
    avl_tree_node_replace(tree, node, new_root);
    (unsafe {
        (*node).children[(1 as i32 as u32).wrapping_sub(direction as u32) as usize] =
            (*new_root).children[direction as usize]
    });
    (unsafe { (*new_root).children[direction as usize] = node });
    (unsafe { (*node).parent = new_root });
    if !(unsafe { (*node).children[(1 as i32 as u32).wrapping_sub(direction as u32) as usize] })
        .is_null()
    {
        (unsafe {
            (*(*node).children[(1 as i32 as u32).wrapping_sub(direction as u32) as usize]).parent =
                node
        });
    }
    avl_tree_update_height(new_root);
    avl_tree_update_height(node);
    return new_root;
}
extern "C" fn avl_tree_node_balance(
    mut tree: *mut AVLTree,
    mut node: *mut AVLTreeNode,
) -> *mut AVLTreeNode {
    let mut left_subtree: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut right_subtree: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut child: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut diff: i32 = 0;
    left_subtree = unsafe { (*node).children[AVL_TREE_NODE_LEFT as i32 as usize] };
    right_subtree = unsafe { (*node).children[AVL_TREE_NODE_RIGHT as i32 as usize] };
    diff = avl_tree_subtree_height(right_subtree) - avl_tree_subtree_height(left_subtree);
    if diff >= 2 {
        child = right_subtree;
        if avl_tree_subtree_height(unsafe {
            (*child).children[AVL_TREE_NODE_RIGHT as i32 as usize]
        }) < avl_tree_subtree_height(unsafe {
            (*child).children[AVL_TREE_NODE_LEFT as i32 as usize]
        }) {
            avl_tree_rotate(tree, right_subtree, AVL_TREE_NODE_RIGHT);
        }
        node = avl_tree_rotate(tree, node, AVL_TREE_NODE_LEFT);
    } else if diff <= -(2 as i32) {
        child = unsafe { (*node).children[AVL_TREE_NODE_LEFT as i32 as usize] };
        if avl_tree_subtree_height(unsafe { (*child).children[AVL_TREE_NODE_LEFT as i32 as usize] })
            < avl_tree_subtree_height(unsafe {
                (*child).children[AVL_TREE_NODE_RIGHT as i32 as usize]
            })
        {
            avl_tree_rotate(tree, left_subtree, AVL_TREE_NODE_LEFT);
        }
        node = avl_tree_rotate(tree, node, AVL_TREE_NODE_RIGHT);
    }
    avl_tree_update_height(node);
    return node;
}
extern "C" fn avl_tree_balance_to_root(mut tree: *mut AVLTree, mut node: *mut AVLTreeNode) {
    let mut rover: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    rover = node;
    while !rover.is_null() {
        rover = avl_tree_node_balance(tree, rover);
        rover = unsafe { (*rover).parent };
    }
}
#[no_mangle]
pub extern "C" fn avl_tree_insert(
    mut tree: *mut AVLTree,
    mut key: AVLTreeKey,
    mut value: AVLTreeValue,
) -> *mut AVLTreeNode {
    let mut rover: *mut *mut AVLTreeNode = 0 as *mut *mut AVLTreeNode;
    let mut new_node: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut previous_node: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    rover = unsafe { &mut (*tree).root_node };
    previous_node = 0 as *mut AVLTreeNode;
    while !(unsafe { *rover }).is_null() {
        previous_node = unsafe { *rover };
        if (unsafe {
            ((*tree).compare_func).expect("non-null function pointer")(key, (**rover).key)
        }) < 0
        {
            rover = (unsafe {
                &mut *((**rover).children)
                    .as_mut_ptr()
                    .offset(AVL_TREE_NODE_LEFT as i32 as isize)
            }) as *mut *mut AVLTreeNode;
        } else {
            rover = (unsafe {
                &mut *((**rover).children)
                    .as_mut_ptr()
                    .offset(AVL_TREE_NODE_RIGHT as i32 as isize)
            }) as *mut *mut AVLTreeNode;
        }
    }
    new_node =
        (unsafe { malloc(::core::mem::size_of::<AVLTreeNode>() as u64) }) as *mut AVLTreeNode;
    if new_node.is_null() {
        return 0 as *mut AVLTreeNode;
    }
    (unsafe { (*new_node).children[AVL_TREE_NODE_LEFT as i32 as usize] = 0 as *mut AVLTreeNode });
    (unsafe { (*new_node).children[AVL_TREE_NODE_RIGHT as i32 as usize] = 0 as *mut AVLTreeNode });
    (unsafe { (*new_node).parent = previous_node });
    (unsafe { (*new_node).key = key });
    (unsafe { (*new_node).value = value });
    (unsafe { (*new_node).height = 1 });
    (unsafe { *rover = new_node });
    avl_tree_balance_to_root(tree, previous_node);
    (unsafe { (*tree).num_nodes = ((*tree).num_nodes).wrapping_add(1) });
    (unsafe { (*tree).num_nodes });
    return new_node;
}
extern "C" fn avl_tree_node_get_replacement(
    mut tree: *mut AVLTree,
    mut node: *mut AVLTreeNode,
) -> *mut AVLTreeNode {
    let mut left_subtree: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut right_subtree: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut result: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut child: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut left_height: i32 = 0;
    let mut right_height: i32 = 0;
    let mut side: i32 = 0;
    left_subtree = unsafe { (*node).children[AVL_TREE_NODE_LEFT as i32 as usize] };
    right_subtree = unsafe { (*node).children[AVL_TREE_NODE_RIGHT as i32 as usize] };
    if left_subtree.is_null() && right_subtree.is_null() {
        return 0 as *mut AVLTreeNode;
    }
    left_height = avl_tree_subtree_height(left_subtree);
    right_height = avl_tree_subtree_height(right_subtree);
    if left_height < right_height {
        side = AVL_TREE_NODE_RIGHT as i32;
    } else {
        side = AVL_TREE_NODE_LEFT as i32;
    }
    result = unsafe { (*node).children[side as usize] };
    while !(unsafe { (*result).children[(1 as i32 - side) as usize] }).is_null() {
        result = unsafe { (*result).children[(1 as i32 - side) as usize] };
    }
    child = unsafe { (*result).children[side as usize] };
    avl_tree_node_replace(tree, result, child);
    avl_tree_update_height(unsafe { (*result).parent });
    return result;
}
#[no_mangle]
pub extern "C" fn avl_tree_remove_node(mut tree: *mut AVLTree, mut node: *mut AVLTreeNode) {
    let mut swap_node: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut balance_startpoint: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut i: i32 = 0;
    swap_node = avl_tree_node_get_replacement(tree, node);
    if swap_node.is_null() {
        avl_tree_node_replace(tree, node, 0 as *mut AVLTreeNode);
        balance_startpoint = unsafe { (*node).parent };
    } else {
        if (unsafe { (*swap_node).parent }) == node {
            balance_startpoint = swap_node;
        } else {
            balance_startpoint = unsafe { (*swap_node).parent };
        }
        i = 0;
        while i < 2 {
            (unsafe { (*swap_node).children[i as usize] = (*node).children[i as usize] });
            if !(unsafe { (*swap_node).children[i as usize] }).is_null() {
                (unsafe { (*(*swap_node).children[i as usize]).parent = swap_node });
            }
            i += 1;
            i;
        }
        (unsafe { (*swap_node).height = (*node).height });
        avl_tree_node_replace(tree, node, swap_node);
    }
    (unsafe { free(node as *mut ()) });
    (unsafe { (*tree).num_nodes = ((*tree).num_nodes).wrapping_sub(1) });
    (unsafe { (*tree).num_nodes });
    avl_tree_balance_to_root(tree, balance_startpoint);
}
#[no_mangle]
pub extern "C" fn avl_tree_remove(mut tree: *mut AVLTree, mut key: AVLTreeKey) -> i32 {
    let mut node: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    node = avl_tree_lookup_node(tree, key);
    if node.is_null() {
        return 0;
    }
    avl_tree_remove_node(tree, node);
    return 1;
}
#[no_mangle]
pub extern "C" fn avl_tree_lookup_node(
    mut tree: *mut AVLTree,
    mut key: AVLTreeKey,
) -> *mut AVLTreeNode {
    let mut node: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    let mut diff: i32 = 0;
    node = unsafe { (*tree).root_node };
    while !node.is_null() {
        diff =
            unsafe { ((*tree).compare_func).expect("non-null function pointer")(key, (*node).key) };
        if diff == 0 {
            return node;
        } else if diff < 0 {
            node = unsafe { (*node).children[AVL_TREE_NODE_LEFT as i32 as usize] };
        } else {
            node = unsafe { (*node).children[AVL_TREE_NODE_RIGHT as i32 as usize] };
        }
    }
    return 0 as *mut AVLTreeNode;
}
#[no_mangle]
pub extern "C" fn avl_tree_lookup(mut tree: *mut AVLTree, mut key: AVLTreeKey) -> AVLTreeValue {
    let mut node: *mut AVLTreeNode = 0 as *mut AVLTreeNode;
    node = avl_tree_lookup_node(tree, key);
    if node.is_null() {
        return core::ptr::null_mut();
    } else {
        return unsafe { (*node).value };
    };
}
#[no_mangle]
pub extern "C" fn avl_tree_root_node(mut tree: *mut AVLTree) -> *mut AVLTreeNode {
    return unsafe { (*tree).root_node };
}
#[no_mangle]
pub extern "C" fn avl_tree_node_key(mut node: *mut AVLTreeNode) -> AVLTreeKey {
    return unsafe { (*node).key };
}
#[no_mangle]
pub extern "C" fn avl_tree_node_value(mut node: *mut AVLTreeNode) -> AVLTreeValue {
    return unsafe { (*node).value };
}
#[no_mangle]
pub extern "C" fn avl_tree_node_child(
    mut node: *mut AVLTreeNode,
    mut side: AVLTreeNodeSide,
) -> *mut AVLTreeNode {
    if side as u32 == AVL_TREE_NODE_LEFT as i32 as u32
        || side as u32 == AVL_TREE_NODE_RIGHT as i32 as u32
    {
        return unsafe { (*node).children[side as usize] };
    } else {
        return 0 as *mut AVLTreeNode;
    };
}
#[no_mangle]
pub extern "C" fn avl_tree_node_parent(mut node: *mut AVLTreeNode) -> *mut AVLTreeNode {
    return unsafe { (*node).parent };
}
#[no_mangle]
pub extern "C" fn avl_tree_num_entries(mut tree: *mut AVLTree) -> u32 {
    return unsafe { (*tree).num_nodes };
}
extern "C" fn avl_tree_to_array_add_subtree(
    mut subtree: *mut AVLTreeNode,
    mut array: *mut AVLTreeValue,
    mut index: *mut i32,
) {
    if subtree.is_null() {
        return;
    }
    avl_tree_to_array_add_subtree(
        unsafe { (*subtree).children[AVL_TREE_NODE_LEFT as i32 as usize] },
        array,
        index,
    );
    let fresh0 = unsafe { &mut (*array.offset(*index as isize)) };
    *fresh0 = unsafe { (*subtree).key };
    (unsafe { *index += 1 });
    (unsafe { *index });
    avl_tree_to_array_add_subtree(
        unsafe { (*subtree).children[AVL_TREE_NODE_RIGHT as i32 as usize] },
        array,
        index,
    );
}
#[no_mangle]
pub extern "C" fn avl_tree_to_array(mut tree: *mut AVLTree) -> *mut AVLTreeValue {
    let mut array: *mut AVLTreeValue = 0 as *mut AVLTreeValue;
    let mut index: i32 = 0;
    array = (unsafe {
        malloc(
            (::core::mem::size_of::<AVLTreeValue>() as u64).wrapping_mul((*tree).num_nodes as u64),
        )
    }) as *mut AVLTreeValue;
    if array.is_null() {
        return 0 as *mut AVLTreeValue;
    }
    index = 0;
    avl_tree_to_array_add_subtree(unsafe { (*tree).root_node }, array, &mut index);
    return array;
}
